#include <bits/stdc++.h>

using namespace std;

const int maxn=(1U<<31)-1;
const int mxlg=31;

int f[mxlg+3][mxlg+3];
inline void getF(){
	f[0][0]=1;
	for(int i=1;i<mxlg;i++){
		f[i][0]=1;
		for(int j=1;j<=i;j++) f[i][j]=f[i-1][j-1]+f[i-1][j];
	}
}
int b;
inline int convert(int x){
	bool flag=0;
    char *sta=new char[mxlg];
    int head=0,ans=0;

    while(x){
        sta[head++]=x%b;
        x/=b;
    }
    for(int i=head-1;i>=0;i--){
        ans<<=1;
        if(flag) ans|=1;
        else{
            if(sta[i]==1) ans|=1;
            else if(sta[i]) flag=1,ans|=1;
        }
    }

    return ans;
}

//[0,x)
inline int solve(const int &x,int k){
    int mask,lg,ans;
    ans=0;
    for(mask=1<<(mxlg-1),lg=mxlg;mask&&k>=0;mask>>=1,lg--)
        if(x&mask) {ans+=f[lg-1][k];k--;}
    return ans;
}

int main(){
    ios::sync_with_stdio(false);
    int x,y,k,t;
    cin>>x>>y>>k>>b;
    getF();
    int ans=solve(t=convert(y),k)-solve(convert(x),k);
    int cnt=0;
    for(int mask=1<<(mxlg-1);mask;mask>>=1) if(t&mask) cnt++;
    if(cnt==k) ans++;
    cout<<ans<<endl;
    return 0;
}
